package com.fengye.algorithms.leecode.dp;

/**
 * @author loupf50246
 * @date 2023/7/9 19:24
 */
public class PartitionTwoEquals416 {
    public static void main(String[] args) {
    }

    public static boolean capPartition(int[] nums) {
        // 求和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 如果是奇数，返回false
        if ((sum & 1) == 1) {
            return false;
        }

        // sum / 2 取目标值
        int target = sum >> 1;
        int length = nums.length;
        int[][] dp = new int[length+1][target+1];
        for (int i=1; i<=length;i++) {
            for (int j=1; j <= target; j++) {
                if (j >= nums[i-1]) {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i-1][j-nums[i-1]]+nums[i-1]);
                } else {
                    dp[i][j] = dp[i-1][j];
                }
            }
        }

        // 判断背包最大是否能存放和为target的元素
        return dp[length][target] == target;
    }

    public static boolean canPartition(int[] nums) {
        // 求和
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }

        // 如果是奇数，返回false
        if ((sum & 1) == 1) {
            return false;
        }

        // sum / 2 取目标值
        int target = sum >> 1;
        int length = nums.length;
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
        for (int i=1; i<= length;i++) {
            for(int j=target;j>=0;j--) {
                if (j >= nums[i-1]) {
                    dp[j] = (dp[j] || dp[j-nums[i-1]]);
                }
            }
        }
        return dp[target];
    }
}
